4208. Степени двойки

Ни для кого не секрет, что число 2ⁿ при любом целом неотрицательном n в двоичной системе счисления имеет очень простой вид – в старшем разряде стоит единица, а затем следует n нулей. В десятичной системе счисления эти числа не столь однообразны, однако и среди них встречаются те, которые начинаются с единицы.

Вычислите, сколько таких чисел в заданном диапазоне.

Вход. Два целых числа n₁ и n₂ (0 ≤ n₁ < n₂ ≤ 10⁹), разделенные пробелом.

Выход. Вывести количество чисел, являющихся степенями двойки и принадлежащих отрезку [2ⁿ¹; 2ⁿ²], у которых в десятичной системе счисления в старшем разряде стоит единица.

Пример входа

0 10

Пример выхода

4

РЕШЕНИЕ

математика – логарифмы

Анализ алгоритма

Среди всех n-значных чисел от 10^n-1 до 10ⁿ – 1 всегда существует одно и только одно число, начинающееся с единицы и являющееся степенью двойки. Например, среди двузначных таким будет число 16, среди трехзначных 128, четырехзначных 1024 и так далее. Отсюда можно заключить, что количество чисел на интервале [1 .. 2^k], являющихся степенью двойки и начинающихся с единицы, равно количеству цифр в десятичном представлении числа 2^k. Обозначим его через f(k). Тогда количество искомых чисел на интервале [2ⁿ¹; 2ⁿ²] равно f(n₂) – f(n₁ – 1).

Количество цифр в десятичном представлении числа n равно . Число 2^k состоит из цифр.

Реализация алгоритма

Читаем входные данные. Вычисляем и выводим ответ. Воспользуемся равенством = чтобы формула работала корректно и для случая n₁ = 0.

scanf("%d %d",&n1,&n2); n1--;

d1 = (int)(n1*log10(2.0) + 1);

d2 = (int)(n2*log10(2.0) + 1);

printf("%d\n",d2 - d1);